package com.zhz.leetcode.sort;

import java.util.Arrays;

/**
 * 插入排序
 * 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
 * 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
 * 如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。
 * <p>
 * https://www.runoob.com/w3cnote/insertion-sort.html
 */
public class InsertSort {

    public static void main(String[] args) {
        InsertSort m = new InsertSort();
        int[] nums = {6, 5, 3, 1, 4, 2, 8, 7};
        m.sort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void sort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int tmp = nums[i];
            int j = i;
            while (j > 0 && tmp < nums[j - 1]) {
                nums[j] = nums[j-1];
                j--;
            }
            if(j!=i){
                nums[j] = tmp;
            }
        }


    }

}
